// bslalg_hashtableanchor.h                                           -*-C++-*-
#ifndef INCLUDED_BSLALG_HASHTABLEANCHOR
#define INCLUDED_BSLALG_HASHTABLEANCHOR

#include <bsls_ident.h>
BSLS_IDENT("$Id: $")

//@PURPOSE: Provide a type holding the constituent parts of a hash table.
//
//@CLASSES:
// bslalg::HashTableAnchor: (in-core) bucket-array and node list
//
//@SEE_ALSO: bslstl_hashtable, bslalg_hashtableimputil
//
//@DESCRIPTION: This component provides a single, complex-constrained
// **in-core** (value-semantic) attribute class, `bslalg::HashTableAnchor`,
// that is used to hold (not own) the array of buckets and the list of nodes
// that form the key data elements of a hash-table.  This class is typically
// used with the utilities provided in `bslstl_hashtableimputil`.  Note that
// the decision to store nodes in a linked list (i.e., resolving collisions
// through chaining) is intended to facilitate a hash-table implementation
// meeting the requirements of a C++11 standard unordered container.
//
///Attributes
///----------
// ```
// Name                Type                  Simple Constraints
// ------------------  -------------------   ------------------
// bucketArrayAddress  HashTableBucket *     none
//
// bucketArraySize     size_t                none
//
// listRootAddress     BidirectionalLink *   none
//
//
// Complex Constraint
// -------------------------------------------------------------------------
// `bucketArrayAddress` must refer to a contiguous sequence of valid
// `bslalg::HashTableBucket` objects of at least the specified
// `bucketArraySize` or both `bucketArrayAddress` and `bucketArraySize` must
// be 0.
// ```
//
// * `listRootAddress`: address of the head of the linked list of nodes
//   holding the elements contained in a hash table
// * `bucketArrayAddress`: address of the first element of the sequence of
//   `HashTableBucket` objects, each of which refers to the first and last
//   node (from `listRootAddress`) in that bucket
// * `bucketArraySize`: the number of (contiguous) buckets in the array of
//   buckets at `bucketArrayAddress`
//
///Usage
///-----
// This section illustrates intended use of this component.
//
///Example 1: Basic Usage
/// - - - - - - - - - - -
// Suppose we want to create a hash table that keeps track of pointers.
// Pointers can be added (`insert`ed) or removed (`erase`d) from the table, and
// the table will keep track, at any time, of whether a pointer is currently
// stored in the table using the `count` method.  It will also be able to
// return the total number of objects stored in the table (the `size` method).
// Redundant `insert`s have no effect -- a given pointer may only be stored in
// the table once.
//
// First, we create our class:
// ```
// class PtrHashSet : public bslalg::HashTableAnchor {
//     // PRIVATE TYPES
//     typedef bsls::Types::UintPtr              UintPtr;
//     typedef bslalg::BidirectionalNode<void *> Node;
//     typedef bslalg::HashTableBucket           Bucket;
//     typedef bslalg::BidirectionalLinkListUtil Util;
//
//     // DATA
//     double            d_maxLoadFactor;
//     unsigned          d_numNodes;
//     bslma::Allocator *d_allocator_p;
//
//     // PRIVATE MANIPULATORS
//
//     /// Roughly double the number of buckets, such that the number of
//     /// buckets shall always be `2^N - 1`.
//     void grow();
//
//     // PRIVATE ACCESSORS
//
//     /// Perform sanity checks on this table, returning `true` if all the
//     /// tests pass and `false` otherwise.  Note that many of the checks
//     /// are done with the `ASSERTV` macro and will cause messages to be
//     /// written to the console.
//     bool checkInvariants() const;
//
//     /// If the specified value `ptr` is stored in this table, return
//     /// pointers to its node and bucket in the specified 'node' and
//     /// `bucket`.  If it is not in this table, return the bucket it
//     /// should be in, and a pointer to the first node, if any, in that
//     /// bucket.  If the bucket is empty, return with
//     /// `*node == listRootAddress()`.  Return `true` if `ptr` was found
//     /// in the table and `false` otherwise.  Note that it is permissible
//     /// to pass 0 to `node` and / or `bucket`, in which case these
//     /// arguments are ignored.
//     bool find(Node **node, Bucket **bucket, const void *ptr) const;
//
//   private:
//     // NOT IMPLEMENTED
//     PtrHashSet(const PtrHashSet&, bslma::Allocator *);
//     PtrHashSet& operator=(const PtrHashSet&);
//
//   public:
//     // CREATORS
//
//     /// Create a `PtrHashSet`, using the specified `allocator`.  If no
//     /// allocator is specified, use the default allocator.
//     explicit
//     PtrHashSet(bslma::Allocator *allocator = 0);
//
//     /// Destroy this `PtrHashSet`, freeing all its memory.
//     ~PtrHashSet();
//
//     // MANIPULATORS
//
//     /// If the specfied `ptr` is not in this hash table, add it,
//     /// returning `true`.  If it is already in the table, return `false`
//     /// with no action taken.
//     bool insert(void *ptr);
//
//     /// If the specfied `ptr` is in this hash table, remove it,
//     /// returning `true`.  If it is not found in the table, return
//     /// `false` with no action taken.
//     bool erase(void *ptr);
//
//     // ACCESSORS
//
//     /// Return 1 if the specified value `ptr` is in this table and 0
//     /// otherwise.
//     std::size_t count(void *ptr) const;
//
//     /// Return the number of discrete values that are stored in this
//     /// table.
//     std::size_t size() const;
// };
//
// // PRIVATE MANIPULATORS
// void PtrHashSet::grow()
// {
//     // 'bucketArraySize' will always be '2^N - 1', so that when pointers
//     // are aligned by some 2^N they're likely to be relatively prime.
//
//     std::size_t newBucketArraySize = bucketArraySize() * 2 + 1;
//     std::size_t newBucketArraySizeInBytes =
//                                        newBucketArraySize * sizeof(Bucket);
//     memset(bucketArrayAddress(), 0x5a, size() * sizeof(Bucket));
//     d_allocator_p->deallocate(bucketArrayAddress());
//     setBucketArrayAddressAndSize(
//              (Bucket *) d_allocator_p->allocate(newBucketArraySizeInBytes),
//              newBucketArraySize);
//     memset(bucketArrayAddress(), 0, newBucketArraySizeInBytes);
//     Node *newListRootAddress = 0;
//
//     unsigned numNodes = 0;
//     for (Node *node = (Node *) listRootAddress(); node; ++numNodes) {
//         Node *rippedOut = node;
//         node = (Node *) node->nextLink();
//
//         std::size_t index =
//                           (UintPtr) rippedOut->value() % bucketArraySize();
//         Bucket& bucket = bucketArrayAddress()[index];
//         if (bucket.first()) {
//             if (0 == bucket.first()->previousLink()) {
//                 newListRootAddress = rippedOut;
//             }
//             Util::insertLinkBeforeTarget(rippedOut, bucket.first());
//             bucket.setFirst(rippedOut);
//         }
//         else {
//             Util::insertLinkBeforeTarget(rippedOut,
//                                          newListRootAddress);
//             newListRootAddress = rippedOut;
//             bucket.setFirstAndLast(rippedOut, rippedOut);
//         }
//     }
//     assert(size() == numNodes);
//
//     setListRootAddress(newListRootAddress);
//
//     checkInvariants();
// }
//
// // PRIVATE ACCESSORS
// bool PtrHashSet::checkInvariants() const
// {
//     bool ok;
//
//     unsigned numNodes = 0;
//     Node *prev = 0;
//     for (Node *node = (Node *) listRootAddress(); node;
//                            prev = node, node = (Node *) node->nextLink()) {
//         ok = node->previousLink() == prev;
//         assert(ok && "node->previousLink() == prev");
//         if (!ok) return false;                                    // RETURN
//         ++numNodes;
//     }
//     ok = size() == numNodes;
//     assert(ok && "size() == numNodes");
//     if (!ok) return false;                                        // RETURN
//
//     numNodes = 0;
//     for (unsigned i = 0; i < bucketArraySize(); ++i) {
//         Bucket& bucket = bucketArrayAddress()[i];
//         if (bucket.first()) {
//             ++numNodes;
//             for (Node *node = (Node *) bucket.first();
//                               bucket.last() != node;
//                                         node = (Node *) node->nextLink()) {
//                 ++numNodes;
//             }
//         }
//         else {
//             ok = !bucket.last();
//             assert(ok && "!bucket.last()");
//             if (!ok) return false;                                // RETURN
//         }
//     }
//     ok = size() == numNodes;
//     assert(ok && "size() == numNodes");
//
//     return ok;
// }
//
// bool PtrHashSet::find(Node **node, Bucket **bucket, const void *ptr) const
// {
//     Node   *dummyNodePtr;
//     Bucket *dummyBucketPtr;
//     if (!node  ) node   = &dummyNodePtr;
//     if (!bucket) bucket = &dummyBucketPtr;
//
//     Node *& nodePtrRef = *node;
//     unsigned index = (UintPtr) ptr % bucketArraySize();
//     Bucket& bucketRef = bucketArrayAddress()[index];
//     *bucket = &bucketRef;
//     if (bucketRef.first()) {
//         Node *begin      = (Node *) bucketRef.first();
//         Node * const end = (Node *) bucketRef.last()->nextLink();
//         for (Node *n = begin; end != n; n = (Node *) n->nextLink()) {
//             if (n->value() == ptr) {
//                 // found
//
//                 nodePtrRef = n;
//                 return true;                                      // RETURN
//             }
//         }
//         // not found
//
//         nodePtrRef = begin;
//         return false;                                             // RETURN
//     }
//     // empty bucket
//
//     nodePtrRef = (Node *) listRootAddress();
//     return false;
// }
//
// // CREATORS
// PtrHashSet::PtrHashSet(bslma::Allocator *allocator)
// : HashTableAnchor(0, 0, 0)
// , d_maxLoadFactor(0.4)
// , d_numNodes(0)
// {
//     enum { NUM_BUCKETS = 3 };
//
//     d_allocator_p = bslma::Default::allocator(allocator);
//     std::size_t bucketArraySizeInBytes = NUM_BUCKETS * sizeof(Bucket);
//
//     setBucketArrayAddressAndSize(
//                 (Bucket *) d_allocator_p->allocate(bucketArraySizeInBytes),
//                 NUM_BUCKETS);
//     memset(bucketArrayAddress(), 0, bucketArraySizeInBytes);
// }
//
// PtrHashSet::~PtrHashSet()
// {
//     BSLS_ASSERT_SAFE(checkInvariants());
//
//     for (Node *node = (Node *) listRootAddress(); node; ) {
//         Node *toDelete = node;
//         node = (Node *) node->nextLink();
//
//         memset(toDelete, 0x5a, sizeof(*toDelete));
//         d_allocator_p->deallocate(toDelete);
//     }
//
//     d_allocator_p->deallocate(bucketArrayAddress());
// }
//
// // MANIPULATORS
// bool PtrHashSet::erase(void *ptr)
// {
//     Bucket *bucket;
//     Node   *node;
//
//     if (!find(&node, &bucket, ptr)) {
//         return false;                                             // RETURN
//     }
//
//     if (bucket->first() == node) {
//         if (bucket->last() == node) {
//             bucket->reset();
//         }
//         else {
//             bucket->setFirst(node->nextLink());
//         }
//     }
//     else if (bucket->last() == node) {
//         bucket->setLast(node->previousLink());
//     }
//
//     --d_numNodes;
//     Util::unlink(node);
//
//     d_allocator_p->deallocate(node);
//
//     checkInvariants();
//
//     return true;
// }
//
// bool PtrHashSet::insert(void *ptr)
// {
//     Bucket *bucket;
//     Node *insertionPoint;
//
//     if (find(&insertionPoint, &bucket, ptr)) {
//         // Already in set, do nothing.
//
//         return false;                                             // RETURN
//     }
//
//     if (bucketArraySize() * d_maxLoadFactor < d_numNodes + 1) {
//         grow();
//         bool found = find(&insertionPoint, &bucket, ptr);
//         BSLS_ASSERT_SAFE(!found);
//     }
//
//     ++d_numNodes;
//     Node *node = (Node *) d_allocator_p->allocate(sizeof(Node));
//
//     Util::insertLinkBeforeTarget(node, insertionPoint);
//     node->value() = ptr;
//     if (listRootAddress() == insertionPoint) {
//         BSLS_ASSERT_SAFE(0 == node->previousLink());
//         setListRootAddress(node);
//     }
//
//     if (bucket->first()) {
//         BSLS_ASSERT_SAFE(bucket->first() == insertionPoint);
//
//         bucket->setFirst(node);
//     }
//     else {
//         BSLS_ASSERT_SAFE(!bucket->last());
//
//         bucket->setFirstAndLast(node, node);
//     }
//
//     assert(count(ptr));
//
//     checkInvariants();
//
//     return true;
// }
//
// // ACCESSORS
// std::size_t PtrHashSet::count(void *ptr) const
// {
//     return find(0, 0, ptr);
// }
//
// std::size_t PtrHashSet::size() const
// {
//     return d_numNodes;
// }
// ```
// Then, in `main`, we create a test allocator for use in this example to
// ensure that no memory is leaked:
// ```
// bslma::TestAllocator ta("test", veryVeryVeryVerbose);
// ```
// Next, we declare our table using that allocator:
// ```
// PtrHashSet phs(&ta);
// ```
// Then, we create an area of memory from which our pointers will come:
// ```
// enum { SEGMENT_LENGTH = 1000 };
// char *pc = (char *) ta.allocate(SEGMENT_LENGTH);
// ```
// Next, we iterate through the length of the segment, insert those pointers
// for which `ptr - pc == N * 7` is true.  We keep a count of the number of
// items we insert into the table in the variable `sevens`:
// ```
// unsigned sevens = 0;
// for (int i = 0; i < SEGMENT_LENGTH; i += 7) {
//     ++sevens;
//     bool status = phs.insert(&pc[i]);
//     assert(status);
// }
// ```
// Then, we verify the number of objects we've placed in the table:
// ```
// assert(phs.size() == sevens);
// ```
// Next, we iterate through ALL pointers in the `pc` array, using the `count`
// method to verify that the ones we expect are in the table:
// ```
// for (int i = 0; i < SEGMENT_LENGTH; ++i) {
//     assert(phs.count(&pc[i]) == (0 == i % 7));
// }
// ```
// Then, we iterate, deleting all elements from the table for which
// `ptr - pc == 3 * N` is true.  We keep a count of the number of elements that
// were deleted from the table in the variable `killed`:
// ```
// unsigned killed = 0;
// for (int i = 0; i < SEGMENT_LENGTH; i += 3) {
//     const bool deleted = phs.erase(&pc[i]);
//     assert(deleted == (0 == i % 7));
//     killed += deleted;
// }
// ```
// Next, we verify the number of remaining elements in the table:
// ```
// assert(killed < sevens);
// assert(phs.size() == sevens - killed);
// ```
// Then, in verbose mode we print our tallies:
// ```
// if (verbose) {
//     printf("sevens = %u, killed = %u, phs.size() = %u\n", sevens,
//            killed, (unsigned) phs.size());
// }
// ```
// Now, we iterate through every element of the `pc` array, verifying that the
// surviving elements are exactly those for which `ptr - pc` was divisible by 7
// and not by 3:
// ```
// for (int i = 0; i < SEGMENT_LENGTH; ++i) {
//     const bool present = phs.count(&pc[i]);
//     assert(present == ((0 == i % 7) && (0 != i % 3)));
// }
// ```
// Finally, we clean up our `pc` array:
// ```
// ta.deallocate(pc);
// ```

#include <bslscm_version.h>

#include <bslalg_bidirectionallink.h>
#include <bslalg_scalarprimitives.h>

#include <bslmf_isbitwisecopyable.h>
#include <bslmf_nestedtraitdeclaration.h>

#include <bsls_assert.h>

#include <cstddef>

#ifndef BDE_DONT_ALLOW_TRANSITIVE_INCLUDES
#include <bsls_nativestd.h>
#endif // BDE_DONT_ALLOW_TRANSITIVE_INCLUDES

namespace BloombergLP {

namespace bslalg {

struct HashTableBucket;  // This is known to be a POD struct.

                        // =============================
                        // class bslalg::HashTableAnchor
                        // =============================

/// This complex constrained *in*-*core* (value-semantic) attribute class
/// characterizes the key data elements of a hash table.  See the
/// [](#Attributes) section information on the class attributes.  Note that the
/// class invariant is the identically the complex constraint of this
/// component.
///
/// This class:
/// * supports a complete set of *value-semantic* operations
///   - except for `bdex` serialization and default construction
/// * is **in-core**
/// * is **exception-neutral** (agnostic)
/// * is **alias-safe**
/// * is `const` **thread-safe**
/// For terminology see `bsldoc_glossary`.
class HashTableAnchor {

    // DATA
    HashTableBucket     *d_bucketArrayAddress_p;  // address of the array of
                                                  // buckets (held, not owned)

    std::size_t          d_bucketArraySize;       // size of 'd_bucketArray'

    BidirectionalLink   *d_listRootAddress_p;     // head of the list of
                                                  // elements in the hash-table
                                                  // (held, not owned)

  public:
    // TRAITS
    BSLMF_NESTED_TRAIT_DECLARATION(HashTableAnchor,
                                   bslmf::IsBitwiseCopyable);

    // CREATORS

    /// Create a `bslalg::HashTableAnchor` object having the specified
    /// `bucketArrayAddress`, `bucketArraySize`, and `listRootAddress`
    /// attributes.  The behavior is undefined unless `bucketArrayAddress`
    /// refers to a contiguous sequence of valid `bslalg::HashTableBucket`
    /// objects of at least `bucketArraySize` or unless both
    /// `bucketArrayAddress` and `bucketArraySize` are 0.
    HashTableAnchor(HashTableBucket   *bucketArrayAddress,
                    std::size_t        bucketArraySize,
                    BidirectionalLink *listRootAddress);

    /// Create a `bslalg::HashTableAnchor` object having the same value
    /// as the specified `original` object.
    //! HashTableAnchor(const HashTableAnchor& original) = default;

    /// Destroy this object.
    //! ~HashTableAnchor(); = default

    // MANIPULATORS

    /// Assign to this object the value of the specified `rhs` object, and
    /// return a reference providing modifiable access to this object.
    //! HashTableAnchor& operator=(const HashTableAnchor& rhs) = default;

    /// Set the bucket array address and bucket array size attributes of
    /// this object to the specified `bucketArrayAddress` and
    /// `bucketArraySize` values.  The behavior is undefined unless
    /// `bucketArrayAddress` refers to a contiguous sequence of valid
    /// `bslalg::HashTableBucket` objects of at least `bucketArraySize`, or
    /// unless both `bucketArrayAddress` and `bucketArraySize` are 0.
    void setBucketArrayAddressAndSize(HashTableBucket *bucketArrayAddress,
                                      std::size_t      bucketArraySize);

    /// Set the `listRootAddress` attribute of this object to the
    /// specified `value`.
    void setListRootAddress(BidirectionalLink *value);

                                  // Aspects

    /// Efficiently exchange the value of this object with the value of the
    /// specified `other` object.  This method provides the no-throw
    /// exception-safety guarantee.
    void swap(HashTableAnchor& other);

    // ACCESSORS

    /// Return the value of the `bucketArrayAddress` attribute of this
    /// object.
    HashTableBucket *bucketArrayAddress() const;

    /// Return the value of the `bucketArraySize` attribute of this object.
    std::size_t bucketArraySize() const;

    /// Return the value `listRootAddress` attribute of this object.
    BidirectionalLink *listRootAddress() const;
};

// FREE OPERATORS

/// Return `true` if the specified `lhs` and `rhs` objects have the same value,
/// and `false` otherwise.  Two `bslalg::HashTableAnchor` objects have the same
/// value if all of the corresponding values of their `bucketArrayAddress`,
/// `bucketArraySize`, and `listRootAddress` attributes are the same.
bool operator==(const HashTableAnchor& lhs, const HashTableAnchor& rhs);

/// Return `true` if the specified `lhs` and `rhs` objects do not have the same
/// value, and `false` otherwise.  Two `bslalg::HashTableAnchor` objects do not
/// have the same value if any of the corresponding values of their
/// `bucketArrayAddress`, `bucketArraySize`, or `listRootAddress` attributes
/// are not the same.
bool operator!=(const HashTableAnchor& lhs, const HashTableAnchor& rhs);

// FREE FUNCTIONS

/// Efficiently exchange the values of the specified `a` and `b` objects.  This
/// function provides the no-throw exception-safety guarantee.  The behavior is
/// undefined unless the two objects were created with the same allocator.
void swap(HashTableAnchor& a, HashTableAnchor& b);

// ============================================================================
//                      INLINE FUNCTION DEFINITIONS
// ============================================================================

                        // -----------------------------
                        // class bslalg::HashTableAnchor
                        // -----------------------------

// CREATORS
inline
HashTableAnchor::HashTableAnchor(bslalg::HashTableBucket   *bucketArrayAddress,
                                 std::size_t                bucketArraySize,
                                 bslalg::BidirectionalLink *listRootAddress)
: d_bucketArrayAddress_p(bucketArrayAddress)
, d_bucketArraySize(bucketArraySize)
, d_listRootAddress_p(listRootAddress)
{
    BSLS_ASSERT_SAFE(   (!bucketArrayAddress && !bucketArraySize)
                     || (bucketArrayAddress && 0 < bucketArraySize));
    BSLS_ASSERT_SAFE(!listRootAddress || !(listRootAddress->previousLink()));
}

// MANIPULATORS
inline
void HashTableAnchor::setBucketArrayAddressAndSize(
                                           HashTableBucket *bucketArrayAddress,
                                           std::size_t      bucketArraySize)
{
    BSLS_ASSERT_SAFE(( bucketArrayAddress && 0 < bucketArraySize)
                  || (!bucketArrayAddress &&    !bucketArraySize));

    d_bucketArrayAddress_p = bucketArrayAddress;
    d_bucketArraySize      = bucketArraySize;
}

inline
void HashTableAnchor::setListRootAddress(BidirectionalLink *value)
{
    BSLS_ASSERT_SAFE(!value || !value->previousLink());

    d_listRootAddress_p = value;
}

                                  // Aspects

inline
void HashTableAnchor::swap(HashTableAnchor& other)
{
    bslalg::ScalarPrimitives::swap(*this, other);
}

// ACCESSORS
inline
BidirectionalLink *HashTableAnchor::listRootAddress() const
{
    return d_listRootAddress_p;
}

inline
std::size_t HashTableAnchor::bucketArraySize() const
{
    return d_bucketArraySize;
}

inline
HashTableBucket *HashTableAnchor::bucketArrayAddress() const
{
    return d_bucketArrayAddress_p;
}

}  // close package namespace

// FREE OPERATORS
inline
void bslalg::swap(bslalg::HashTableAnchor& a, bslalg::HashTableAnchor& b)
{
    a.swap(b);
}

inline
bool bslalg::operator==(const bslalg::HashTableAnchor& lhs,
                        const bslalg::HashTableAnchor& rhs)
{
    return lhs.bucketArrayAddress() == rhs.bucketArrayAddress()
        && lhs.bucketArraySize()    == rhs.bucketArraySize()
        && lhs.listRootAddress()    == rhs.listRootAddress();
}

inline
bool bslalg::operator!=(const bslalg::HashTableAnchor& lhs,
                        const bslalg::HashTableAnchor& rhs)
{
    return lhs.bucketArrayAddress() != rhs.bucketArrayAddress()
        || lhs.bucketArraySize()    != rhs.bucketArraySize()
        || lhs.listRootAddress()    != rhs.listRootAddress();
}

}  // close enterprise namespace

#endif

// ----------------------------------------------------------------------------
// Copyright 2013 Bloomberg Finance L.P.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
// ----------------------------- END-OF-FILE ----------------------------------
